맨위로가기

버킷 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

버킷 정렬은 정렬 알고리즘의 하나로, 데이터를 여러 버킷에 분산시킨 후 각 버킷 내에서 정렬을 수행하는 방식이다. 이 알고리즘은 두 가지 주요 구현 방식을 가지며, 가변 길이 데이터 구조를 사용하는 방법과 값별 출현 횟수를 세어 배열을 분할하는 방법이 있다. 후자는 분포 계수 정렬 또는 계수 정렬이라고도 불린다. 버킷 정렬은 입력 데이터가 균등 분포에 가까울 때 유용하며, 최악의 경우 시간 복잡도는 버킷 내부 정렬 알고리즘에 따라 달라진다. 평균 시간 복잡도는 입력 분포에 따라 O(n)으로 나타날 수 있다. 버킷 정렬은 일반 버킷 정렬, 프록스맵 정렬, 히스토그램 정렬, 우체부 정렬, 셔플 정렬 등 다양한 변형이 존재하며, 다른 정렬 알고리즘과의 비교를 통해 특징을 파악할 수 있다. 또한, 스리프 정렬과 같은 특수한 형태도 존재하지만, 실용적인 사용에는 한계가 있다.

더 읽어볼만한 페이지

  • 안정 정렬 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 안정 정렬 - 삽입 정렬
    삽입 정렬은 미정렬 부분의 원소를 정렬된 부분의 올바른 위치에 삽입하여 정렬을 완성하는 간단하고 효율적인 알고리즘이지만, 데이터 세트가 클수록 성능이 저하되어 이를 개선하기 위한 변형 알고리즘이 존재한다.
  • 정렬 알고리즘 - 합병 정렬
    합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
  • 정렬 알고리즘 - 퀵 정렬
    퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
버킷 정렬
알고리즘 정보
분류정렬 알고리즘
자료 구조배열
최악 시간 복잡도O(n^2)
평균 시간 복잡도O(n+ rac{n^2}{k}+k), k는 버킷 수. O(n), ext {when } k pprox n.
공간 복잡도O(n + k)
최선 시간 복잡도O(n)

2. 알고리즘

버킷 정렬은 정렬할 배열을 일정한 크기의 '버킷'으로 나누고, 각 버킷을 개별적으로 정렬한 후 다시 합치는 방식으로 작동한다.
기본 작동 방식1. 버킷 나누기: 정렬할 데이터의 범위를 기준으로, 여러 개의 버킷을 생성한다. 예를 들어, 0부터 100 사이의 숫자를 정렬한다면, 10개의 버킷을 만들어 각각 0-9, 10-19, ..., 90-99 범위를 담당하게 할 수 있다.

2. 데이터 분배: 정렬할 데이터를 순회하면서, 각 데이터의 값에 해당하는 버킷에 넣는다.

3. 버킷 정렬: 각 버킷 내의 데이터를 정렬한다. 이때 삽입 정렬과 같이 간단한 정렬 알고리즘을 사용하거나, 재귀적으로 버킷 정렬을 다시 적용할 수도 있다.

4. 합치기: 정렬된 각 버킷의 데이터를 순서대로 합치면, 전체 데이터가 정렬된다.
구현 방법버킷 정렬은 크게 두 가지 방식으로 구현할 수 있다.


  • 가변 버킷: 각 버킷을 선형 리스트와 같이 크기가 변할 수 있는 자료 구조로 표현한다. 구현이 직관적이지만, 가변 길이 자료 구조를 지원하지 않는 언어에서는 추가적인 구현 비용이 발생할 수 있다.
  • 분포 계수 정렬 (Counting Sort): 정렬할 데이터의 값별 출현 횟수를 세어, 하나의 배열 안에서 각 값의 위치를 계산하는 방식이다.

예시다음과 같은 입력 데이터를 오름차순으로 정렬하는 경우를 생각해 보자.

```

3 2 2 1 2 2 1 3 3 1 2 3

```

1. 값별 출현 횟수: 1은 3개, 2는 5개, 3은 4개 나타난다.

2. 시작 위치: 1은 1번째, 2는 4번째, 3은 9번째부터 시작한다.

3. 정렬 결과: 1 1 1 2 2 2 2 2 3 3 3 3
안정 정렬같은 값을 가진 데이터가 원래 순서대로 정렬되는 것을 '안정 정렬'이라고 한다. 버킷 정렬을 안정 정렬로 구현하려면, 같은 버킷에 있는 데이터는 넣은 순서대로 꺼내야 한다. 기수 정렬과 함께 사용하려면 안정 정렬이어야 한다.

2. 1. 의사 코드

pseudocode

'''function''' bucketSort(array, k) '''is'''

buckets ← new array of k empty lists

M ← the maximum key value in the array

'''for''' i = 1 '''to''' length(array) '''do'''

insert ''array[i]'' into ''buckets[floor(k × array[i] / M)]''

'''for''' i = 1 '''to''' k '''do'''

nextSort(buckets[i])

'''return''' the concatenation of buckets[1], ...., buckets[k]

```

  • `array`는 정렬할 배열, `k`는 사용할 버킷 수이다. 키 값의 최대값은 모든 키를 한 번씩 조회하여 선형 시간에 계산할 수 있다.
  • `floor`는 바닥 함수로써 부동 소수점 수를 정수로 변환한다.
  • `nextSort`는 각 버킷 내부를 정렬하는 함수이다. 일반적으로 삽입 정렬을 사용하지만 다른 알고리즘도 사용할 수 있다.
  • `bucketSort` 자체를 `nextSort`로 사용하면 기수 정렬과 흡사하고, 특히 `n = 2` 이면 (피벗 선택이 나쁜) 퀵 정렬과 동등하다.[1]


```pseudocode

'''함수''' 버킷 정렬(배열, k) '''은'''

버킷 ← k개의 빈 리스트로 구성된 새로운 배열

M ← 배열 내 최대 키 값 + 1

'''다음''' i = 0 '''부터''' 배열 길이까지 '''반복'''

''배열[i]''를 ''버킷[바닥(k × 배열[i] / M)]''에 삽입

'''다음''' i = 0 '''부터''' k까지 '''반복'''

다음정렬(버킷[i])

'''반환''' 버킷[0], ...., 버킷[k]의 연결

```

  • 여기서 ''배열''은 정렬할 배열을 나타내고 ''k''는 사용할 버킷의 수를 나타낸다.
  • 모든 키를 한 번 반복하여 선형 시간에 최대 키 값을 계산할 수 있다.
  • 바닥 함수는 부동 소수점 숫자를 정수로 변환하는 데 사용해야 한다 (그리고 데이터 유형의 캐스팅도 가능).
  • 함수 ''다음정렬''은 각 버킷을 정렬하는 데 사용되는 정렬 함수이다.
  • 일반적으로 삽입 정렬을 사용하지만, ''선택 정렬'' 또는 ''병합 정렬''과 같은 다른 알고리즘도 사용할 수 있다.
  • ''버킷 정렬'' 자체를 ''다음정렬''로 사용하면 기수 정렬의 일종이 생성된다.
  • 특히, ''n = 2''의 경우는 퀵 정렬에 해당한다 (잠재적으로 피벗 선택이 좋지 않더라도).[1]

2. 2. 분석

입력에 서로 가까운 키가 여러 개 포함되어 있을 때(클러스터링), 해당 요소들이 동일한 버킷에 배치될 가능성이 높아 일부 버킷에는 평균보다 많은 요소가 포함된다. 최악의 경우에는 모든 요소가 단일 버킷에 배치될 때 발생하는데, 이때 전체적인 성능은 각 버킷을 정렬하는 데 사용되는 알고리즘에 의해 좌우된다. 예를 들어 O(n^2) 삽입 정렬이나 O(n \log(n)) 비교 정렬 알고리즘(예: 병합 정렬)이 사용될 수 있다.

32비트 정수를 정렬하는 경우, 약 43억 개의 버킷을 갖는 것은 비현실적이다. 버킷은 하나의 값에 대해 하나의 버킷을 준비할 필요는 없으며, 범위를 가진 버킷이 모순 없이 정렬되어 있으면 된다. 이때 각 버킷의 내용은 다른 정렬 알고리즘으로 정렬하거나, 다시 버킷 정렬을 적용할 수 있다.

32비트 정수를 1비트씩 재귀적으로 버킷 정렬하면 32계층의 버킷 정렬이 필요하게 된다. 이는 약 43억 개에 대한 log이며, 버킷 정렬 또한 log의 차수에서 벗어날 수 없다는 것을 알 수 있다. (2비트씩, 4비트씩 처리해도 마찬가지이다.)

일반적으로 각 값의 가능한 범위보다 정렬해야 할 배열 크기가 더 작기 때문에, 버킷 정렬은 O(''n''log''n'') 정렬보다 실질적으로 속도가 느린 경우가 많다.

문자열에 대해서도 머리부터 1자씩 재귀적으로 버킷 정렬을 수행할 수 있다. 32비트 정수 정렬은 길이 32의 1비트 문자로 구성된 문자열을 정렬하고 있다고 간주할 수도 있다.

2. 2. 1. 최악 시간 복잡도

균등 분포에 가깝지 않아, 가까운 값을 가진 키가 여럿인 경우(클러스터를 형성할 경우) 이 키들은 같은 버킷에 들어갈 확률이 높아 어떤 버킷은 다른 버킷보다 더 많은 원소를 가질 수 있다. 최악의 경우에는 모든 원소가 하나의 버킷에 들어갈 수 있다. 이 경우 전체 성능은 버킷 내부를 정렬하는 알고리즘에 따라 결정된다. 주로 삽입 정렬이 이용되므로 O(n^2)이어서, 병합 정렬과 같은 비교 정렬 알고리즘의 O(n \log(n))보다 나빠질 수 있다.[1]

2. 2. 2. 평균 시간 복잡도

입력이 균등하게 분포한다고 가정하면, 버킷 정렬은 평균적으로 선형 시간 복잡도, 즉 O(n)으로 실행된다.[8][3]
단계별 분석:1. 초기화 및 최댓값 찾기: 버킷을 초기화하고 배열에서 최댓값을 찾는 데 O(n) 시간이 소요된다.

2. 분산: 나눗셈과 곱셈이 상수 시간에 가능하다면, 각 원소를 해당 버킷에 분산하는 데에도 O(n) 시간이 걸린다.

3. 버킷 내부 정렬: 각 버킷을 삽입 정렬로 정렬한다고 가정하면, 이 단계의 시간 복잡도는 \(O(\textstyle \sum_{i=1}^k \displaystyle n_i^2)\)이며, 여기서 \(n_i\)는 i번째 버킷의 길이이다. 평균적인 경우를 고려하기 위해 기대값 \(E(n_i^2)\)을 사용한다.

4. 기대값 계산:

  • \(X_{ij}\)를 원소 j가 버킷 i에 있으면 1, 아니면 0인 확률 변수로 정의하면, \(n_i = \sum_{j=1}^n X_{ij}\)이다.
  • \(E(n_i^2)\)는 수식을 통해 전개되며, \(j=l\)인 경우와 \(j \neq l\)인 경우로 나누어 계산된다.
  • 각 원소가 버킷 i에 들어갈 확률은 \(1/k\)이므로, \(E(X_{ij}^2) = 1/k\)이고, \(E(X_{ij}X_{il}) = 1/k^2\)이다.
  • 최종적으로 \(E(n_i^2) = \frac{n^2 + nk - n}{k^2}\)이 된다.

5. 전체 버킷 정렬 복잡도: \(O\left(\sum_{i=1}^kE(n_i^2)\right) = O\left(\frac{n^2}{k}+n\right) \)

6. 연결: 마지막으로 각 버킷을 연결하는 데 O(k) 시간이 걸린다.

따라서 총 시간 복잡도는 \(O\left(n+\frac{n^2}{k}+k\right)\)이다. 만약 k를 \(k = \Theta(n)\)으로 설정하면, 즉 버킷의 개수가 입력 데이터의 개수와 비례하도록 하면, 평균 시간 복잡도는 O(n)이 된다.[8][3]

2. 3. 최적화

일반적인 최적화 방법으로는 먼저 버킷을 정렬되지 않은 채로 원래 배열에 다시 넣은 다음, 전체 배열에 대해 삽입 정렬을 수행하는 것이 있다. 삽입 정렬의 실행 시간은 각 원소가 정렬된 최종 위치에서 얼마나 떨어져 있는지에 따라 결정되므로, 비교 연산 횟수가 상대적으로 적게 유지된다. 또한, 원소 목록이 메모리에 연속적으로 저장되기 때문에 메모리 계층 구조를 더 잘 활용할 수 있다.[9][1]

입력 분포를 알거나 추정할 수 있는 경우에는, 버킷을 단순히 일정한 크기가 아닌 일정한 밀도를 갖도록 선택할 수 있다. 이렇게 하면 균일하게 분포된 입력이 아니더라도 평균 시간 복잡도 O(''n'')을 얻을 수 있다.

32비트 정수를 정렬하는 경우를 예로 들면, 약 43억 개의 버킷을 사용하는 것은 비현실적이다. 버킷은 반드시 하나의 값에 대해 하나의 버킷을 준비할 필요는 없으며, 범위를 가진 버킷들이 모순 없이 정렬되어 있으면 된다. 이때 각 버킷의 내용은 다른 정렬 알고리즘으로 정렬하거나, 다시 버킷 정렬을 적용할 수 있다.

처음에 언급한 32비트 정수를 1비트씩 재귀적으로 버킷 정렬하면, 32계층의 버킷 정렬이 필요하다. 이는 약 43억에 대한 log이며, 버킷 정렬 또한 log의 차수에서 벗어날 수 없음을 보여준다. (2비트씩, 또는 4비트씩 처리해도 log는 사라지지 않는다.)

일반적으로 정렬해야 할 배열의 크기가 각 값의 가능한 범위보다 작기 때문에, 버킷 정렬은 O(''n''log''n'') 정렬보다 실질적으로 느린 경우가 많다.

문자열에 대해서도, 머리부터 한 글자씩 재귀적으로 버킷 정렬을 수행할 수 있다. 32비트 정수 정렬은 길이가 32인 1비트 문자로 구성된 문자열을 정렬하는 것으로 간주할 수도 있다.

3. 종류

버킷 정렬에는 다음과 같은 다양한 종류가 있다.


  • 일반 버킷 정렬: 가장 일반적인 형태로, 0부터 최댓값 ''M'' 사이의 수를 크기가 ''M''/''n''인 ''n''개의 버킷으로 나눈다. 각 버킷을 삽입 정렬로 정렬하면 선형 시간의 기대값으로 수행되는 것처럼 보인다.[10] 하지만 많은 값이 서로 인접해 있으면 성능이 저하될 수 있다. 이러한 성능 저하는 ''[0,1)'' 구간에서 무작위로 발생시킨 값을 입력으로 가정하여 회피한다.[11]
  • 프록스맵 정렬 (ProxmapSort): "맵 키" 함수를 사용하여 키 배열을 부분 배열로 분할한다. 각 키를 하위 배열에 추가할 때 삽입 정렬을 사용하여 정렬된 상태를 유지한다.[1]
  • 히스토그램 정렬 (Histogram sort): 계수 정렬이라고도 하며, 각 버킷에 들어갈 원소의 수를 미리 계산하는 초기화 단계를 거친다.[12][4]
  • 우체부 정렬 (Postman's sort): postman's sort영어은 속성 집합으로 표현되는 원소의 계층 구조를 활용한다. 우체국의 편지 분류기에 사용되는 방식과 유사하며, 최상위 유효숫자 우선 기수 정렬과 유사하다.[13][5]
  • 셔플 정렬 (Shuffle sort): 정렬할 항목 ''n''개 가운데 첫 1/8을 제거하고 재귀적으로 정렬하여 새 배열에 넣는다. 이 방법으로 ''n''/8개의 버킷을 만들어 나머지 7/8을 분산시켜 넣고, 각 버킷은 정렬된 배열로 연결한다.[6]

3. 1. 일반 버킷 정렬

버킷 정렬의 가장 일반적인 형태는 0부터 최댓값 ''M'' 사이의 수를 각각의 크기가 ''M''/''n''인 ''n''개의 버킷으로 나누는 것이다. 각 버킷을 삽입 정렬로 정렬하면 선형 시간의 기대값으로 수행되는 것처럼 보인다. (모든 입력에 대해 평균을 취할 경우).[10] 그러나 많은 값이 서로 인접해 있으면 클러스터를 이루었다고 하며 모두 단일 버킷으로 들어갈 수 있어 성능이 저하된다. 원래의 버킷 정렬 알고리즘은 ''[0,1)'' 구간에서 무작위로 발생시킨 값을 입력으로 취한다고 가정하여 이런 성능 저하를 회피하였다.[11]

정렬하려는 데이터가 가질 수 있는 값이 m 종류일 때, m개의 버킷을 준비하고 값마다 하나의 버킷을 대응시킨다. 원래 데이터 열을 훑어 각 데이터를 해당 버킷에 넣는다. 이 처리가 끝나면 정렬하려는 순서에 따라 버킷에서 값을 꺼내면 데이터를 정렬할 수 있다.

안정 정렬을 구현하려면 같은 버킷에 있는 데이터는 넣을 때와 같은 순서로 꺼내야 한다. 순서가 보존되지 않으면 정렬은 되지만, 안정 정렬이 되지 않는다. 후술할 기수 정렬과 함께 사용하기 위해서는 안정 정렬이어야 한다.

버킷 정렬에는 크게 2가지 구현이 있다.

첫 번째는 가변 개수의 요소를 보관할 수 있는 데이터 구조를 사용하여 버킷을 표현하는 방법이다. 간단한 예시로 m개의 선형 리스트를 사용하는 구현을 생각할 수 있다. 직관적으로 이해하기 쉬운 구현이지만, 단순한 배열뿐만 아니라 가변 길이의 데이터 구조가 필요하므로, 가변 길이의 데이터 구조가 없는 언어의 경우 그 구현 비용을 고려해야 한다.

두 번째는 일단 정렬 대상 데이터를 주사하여 값별 출현 횟수를 세어두고, 그에 따라 하나의 배열 안을 값별로 분할하는 방법이다. 이 구현에 의한 버킷 정렬만을 특히 '''분포 계수 정렬''', '''계수 정렬'''(Counting Sort)이라고 한다.

예를 들어 다음과 같은 입력이 주어졌다고 하자.

: 3 2 2 1 2 2 1 3 3 1 2 3

오름차순으로 정렬한 결과는 다음과 같을 것이다.

: 1 1 1 2 2 2 2 2 3 3 3 3

값별 출현 분포를 조사하면, 1이 3개, 2가 5개, 3이 4개 출현하고 있음을 알 수 있다 (정렬하지 않아도 원래의 데이터 열에 한 번 접근하면 알 수 있다). 출현 개수를 알면, 1은 결과 열의 1번째부터, 2는 4번째부터, 3은 9번째부터 시작함을 알 수 있다.

3. 2. 프록스맵 정렬 (ProxmapSort)

프록스맵 정렬은 일반적인 버킷 정렬과 유사하지만, "맵 키" 함수를 사용하여 키 배열을 부분 배열로 분할한다는 점에서 차이가 있다. 이 맵 키 함수는 키의 반 순서(partial order)를 유지한다. 각 키를 하위 배열에 추가할 때 삽입 정렬을 사용하여 하위 배열을 정렬된 상태로 유지하므로, 전체 배열이 정렬된 상태로 유지된다.[1] 맵 키 함수는 자료를 정렬 순서에 근사한 대략적인 위치로 이동시켜 키의 "프록스맵"(근접성 매핑)을 생성한다는 점에서도 버킷 정렬과 다르다.[1]

3. 3. 히스토그램 정렬 (Histogram sort)

히스토그램 정렬은 계수 정렬이라고도 하며, 각 버킷에 들어갈 원소의 수를 미리 계산하는 초기화 단계를 거친다.[12][4] 이 정보를 활용하면 배열 원소들을 버킷 순서에 따라 위치를 교환하는 것만으로 정렬할 수 있어, 버킷을 위한 별도의 메모리 할당이 필요 없게 된다.[12]

정렬하려는 데이터가 가질 수 있는 값이 m 종류일 때, m개의 버킷을 준비하고 각 값마다 하나의 버킷을 대응시킨다. 데이터를 훑어보면서 각 데이터를 해당 버킷에 넣고, 정렬 순서에 따라 버킷에서 값을 꺼내면 정렬된 데이터를 얻을 수 있다.

같은 버킷에 있는 데이터는 넣을 때와 같은 순서로 꺼내야 안정 정렬이 된다. 기수 정렬과 함께 사용하려면 안정 정렬이어야 한다.

버킷 정렬의 구현 방법에는 두 가지가 있다.

  • 첫 번째는 가변 개수의 요소를 보관할 수 있는 선형 리스트와 같은 데이터 구조를 사용하여 버킷을 표현하는 방법이다.
  • 두 번째는 정렬 대상 데이터를 확인하여 값별 출현 횟수를 세고, 그에 따라 배열을 값별로 분할하는 방법이다. 이 방법을 '''분포 계수 정렬''' 또는 '''계수 정렬'''(Counting Sort)이라고 한다.

예시:다음과 같은 입력값을 오름차순으로 정렬하는 경우를 생각해 보자.

```

3 2 2 1 2 2 1 3 3 1 2 3

```

먼저, 각 값의 출현 횟수를 세면 1은 3개, 2는 5개, 3은 4개이다. 이 정보를 통해 정렬된 배열에서 1은 1번째부터, 2는 4번째부터, 3은 9번째부터 시작한다는 것을 알 수 있다.

3. 4. 우체부 정렬 (Postman's sort)

'''우체부 정렬'''(postman's sort영어)은 속성 집합으로 표현되는 원소의 계층 구조를 활용하는 버킷 정렬의 일종이다. 우체국의 편지 분류기에 사용된다. 우편물은 국내와 국제, 광역지자체, 지역 우체국, 배달 경로 순으로 분류된다. 이 과정에서 각 키를 서로 비교하지 않기 때문에 정렬 시간복잡도는 O(''cn'')이다. ''c''는 키의 크기와 버킷 수에 따라 결정된다. 최상위 유효숫자 우선 기수 정렬과 유사하다.[13][5]

3. 5. 셔플 정렬 (Shuffle sort)

셔플 정렬[14]은 정렬할 항목 ''n''개 가운데 첫 1/8을 제거하고 재귀적으로 정렬하여 새 배열에 넣는다. 이 방법으로 n/8개의 버킷을 만들어 나머지 7/8을 분산시켜 넣고, 각 버킷은 정렬된 배열로 연결한다.[6]

4. 다른 정렬 알고리즘과의 비교

버킷 정렬은 다른 정렬 알고리즘과 비교했을 때 몇 가지 특징을 가진다.


  • 계수 정렬: 버킷 정렬은 계수 정렬의 일반화된 형태로 볼 수 있다. 각 버킷의 크기가 1일 때 버킷 정렬은 계수 정렬과 같아진다. 버킷 정렬은 가변 크기의 버킷을 사용하여 공간 복잡도를 O(''n'')으로 줄일 수 있지만, 계수 정렬의 O(''n'' + ''M'') (''M''은 고유한 값의 개수) 시간 복잡도는 포기해야 한다.

  • 퀵 정렬: 두 개의 버킷을 사용하는 버킷 정렬은 퀵 정렬과 유사하게 작동하며, 피벗 값을 항상 값 범위의 중간 값으로 선택한다. 이는 균등하게 분포된 입력에 효과적이지만, 입력 데이터가 몰려 있으면 성능이 떨어진다. 퀵 정렬에서 무작위로 피벗을 선택하는 방법은 이러한 클러스터링에 더 강하다.

  • 합병 정렬: ''n''-방향 합병 정렬은 목록을 ''n''개의 하위 목록으로 나누고 각 하위 목록을 정렬하는 방식으로 시작한다. 합병 정렬의 하위 목록은 값 범위가 겹치기 때문에 버킷 정렬처럼 단순하게 연결할 수 없고, 병합 알고리즘을 사용해야 한다. 하지만, 이러한 추가 비용은 더 간단한 분산 단계와 각 하위 목록의 동일한 크기를 보장하여 최악의 경우에도 좋은 성능을 제공한다.

  • 기수 정렬: 상향식 기수 정렬은 값의 범위와 버킷 수가 2의 거듭제곱으로 제한되는 특수한 경우의 버킷 정렬이다. 각 버킷의 크기도 2의 거듭제곱이 되며, 재귀적으로 적용할 수 있다. 이 방법은 각 요소의 비트 표현의 접두사만 보고 버킷을 결정할 수 있어 분산 단계를 빠르게 처리할 수 있다.


버킷 정렬은 비교를 수행하지 않고 정렬할 수 있다는 장점이 있지만, 정렬 대상 값의 모델에 맞춰 프로그램을 작성해야 하는 단점도 있다.

5. 스리프 정렬 (Sleep sort)

스리프 정렬(Sleep sort)은 버킷 정렬에서 버킷을 메모리 공간 대신 시간에 치환한 것이다. 원래 4chan 게시판에 게시된 아이디어이다.[7] 각 원소의 값에 비례하는 시간만큼 대기한 후 출력하는 방식이다.

"전 요소의 최댓값 × 잠들게 하는 단위 시간"으로 실제로 정렬할 수 있지만, 이는 예제 수준에서나 가능한 방법이다.

실제 컴퓨터 시스템에서는 시작된 프로세스가 의도한 시간에 정확히 종료된다는 보장이 없다. 비동기적으로 여러 프로세스를 시작하면 혼잡이나 OS의 제어 때문에 값이 반환되는 순서가 의도한 시간과 다를 수 있다. 또한 정렬에서 기대하는 순서와 다른 순서로 반환될 위험도 있다. 따라서 스리프 정렬은 데모나 농담으로는 몰라도, 실용적으로는 절대 사용해서는 안 된다.

OS는 일정 시간 후에 시작하는 요구를 도래 시간 순서대로 대기열에 연결하여 관리한다. 이때 도래 시간의 크고 작음을 비교한다. 타이머로 감시하고, 시간이 도래한 요구를 행렬에서 빼내어 요구처의 대기를 해제하고 결과를 통지하는 것이 OS의 역할이다. 정렬 알고리즘에 필수적인 이 "계산" 비용이 계산량에 포함되지 않아, 마치 계산이 필요 없는 것처럼 보이는 트릭이 있는 것이다. 즉, 시간 순서대로 정렬된 "버킷"을 준비하고 데이터를 넣고 빼는 "숨은 일꾼"이 존재하는 것이다.

bash를 이용한 구현은 다음과 같다.[7]

```bash

#!/bin/bash

function f() {

sleep "$1"

echo "$1"

}

while [ -n "$1" ]

do

f "$1" &

shift

done

wait

```

사용 예시는 아래와 같다.

```console

$ ./sleepsort.bash 5 3 6 3 6 3 1 4 7

1

3

3

3

4

5

6

6

7

```

위 결과는 올바르게 정렬되었다.

그러나 처리 시스템(Windows 10, Cygwin bash)에서 몇 번 실행했을 뿐인데, 통상적인 시간보다 몇 배나 시간이 지난 후, 아래와 같이 일부 순서가 바뀌거나 입력 순서 그대로 나오는 등 잘못된 결과가 나오는 경우가 있었다.

```console

$ ./sleepsort.bash 5 3 6 3 6 3 1 4 7

3

5

6

3

3

6

1

4

7

참조

[1] 간행물 "Sorting in linear time — variations on the bucket sort" 2004-10
[2] 서적 Introduction to Algorithms MIT Press and McGraw-Hill 2001
[3] 서적 Introduction to Algorithms
[4] 웹사이트 NIST's Dictionary of Algorithms and Data Structures: histogram sort https://xlinux.nist.[...]
[5] 웹사이트 Robert Ramey Software Development http://www.rrsd.com/[...]
[6] 웹사이트 A revolutionary new sort from John Cohen https://groups.googl[...] 1997-11-26
[7] 웹사이트 スリープソート http://qiita.com/sns[...]
[8] 서적 Introduction to Algorithms
[9] 문서 Corwin, E. and Logar, A. "Sorting in linear time — variations on the bucket sort".
[10] 문서 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
[11] 서적 Introduction to Algorithms
[12] 웹사이트 NIST's Dictionary of Algorithms and Data Structures: histogram sort https://xlinux.nist.[...]
[13] 웹사이트 http://www.rrsd.com/[...]
[14] 웹사이트 A revolutionary new sort from John Cohen https://groups.googl[...] 1997-11-26


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com